		TITLE	QSORTRES - Copyright (c) SLR Systems 1994

		INCLUDE	MACROS

if	fg_pe

		PUBLIC	RES_SORT,STORE_RES_ECXEAX,INIT_RES_SORT


		.DATA


		.CODE	PASS2_TEXT

		EXTERNDEF	GET_NEW_LOG_BLK:PROC,ERR_ABORT:PROC


QUICK_VARS	STRUC

QDELTA_BP		DD	?
QLEFT_NUMBER_BP		DD	?
QRIGHT_NUMBER_BP	DD	?
Q_OS2_NUMBER_BP		DD	?
QLEFT_PTR_BP		DD	?
QRIGHT_PTR_BP		DD	?
QMIDDLE_PTR_BP		DD	?
Q_TEMP_WORD_BP		DD	?
QN_COUNT_BP		DD	?
QN_BUFFER_PTR_BP	DD	?

QUICK_VARS	ENDS


FIX	MACRO	X

X	EQU	([EBP-SIZE QUICK_VARS].(X&_BP))

	ENDM


FIX	QDELTA
FIX	QLEFT_NUMBER
FIX	QRIGHT_NUMBER
FIX	Q_OS2_NUMBER
FIX	QLEFT_PTR
FIX	QRIGHT_PTR
FIX	QMIDDLE_PTR
FIX	Q_TEMP_WORD
FIX	QN_COUNT
FIX	QN_BUFFER_PTR


RES_SORT	PROC
		;
		;USE QUICKSORT ALGORITHM TO NUMERICAL DATA IN QN_BUFFER
		;
		PUSHM	EBP,EDI,ESI,EBX			;SAVE THAT STACK FRAME

		MOV	EBP,ESP
		SUB	ESP,SIZE QUICK_VARS
		ASSUME	EBP:PTR QUICK_VARS

		MOV	QN_BUFFER_PTR,EAX
		CALL	QSORT_INIT

		CALL	QUICK_LIN

		MOV	EAX,QN_COUNT
		MOV	ESP,EBP

		POPM	EBX,ESI,EDI,EBP

		RET

RES_SORT	ENDP


QUICK_LINNUM_1	PROC	NEAR

QUICK_2:
		;
		;JUST SORT THE TWO AND RETURN...
		;
		CALL	Q_SET_LEFT_BLOCK	;DS:SI

		CALL	Q_SET_RIGHT_BLOCK	;ES:DI

		JMP	QL_SORT2

QUICK3:
		POP	EAX
QUICK2_FINISH:
QUICK_DONE:
		RET

QUICK_LIN::
		;
		;OK BOYS, HERE GOES A QUICK-SORT IMPLEMENTATION...
		;
		;SI IS LEFT LINNUM #, DI IS RIGHT LINNUM #
		;
		MOV	ECX,EDI
QUICK_LIN_1:
		SUB	ECX,ESI
		JNA	QUICK_DONE	;RIGHT <= LEFT, QUIT
		;
		;WHAT ABOUT REAL SMALL CX ?
		;
		INC	ECX
		JZ	QUICK_DONE

		CMP	ECX,2
		JZ	QUICK_2

		MOV	QDELTA,ECX

		SHR	ECX,1
		PUSH	ESI		;SAVE ORIGINAL LEFTY

		ADD	ECX,ESI		;HALF WAY
		MOV	QLEFT_NUMBER,ESI


		MOV	QRIGHT_NUMBER,EDI
		CALL	Q_SET_LEFT_BLOCK	;DS:SI

		MOV	QLEFT_PTR,ESI
		CALL	Q_SET_RIGHT_BLOCK	;ES:DI

		MOV	QRIGHT_PTR,EDI
		CALL	Q_SET_MIDDLE_BLOCK	;ES:DI

		MOV	QMIDDLE_PTR,EDI
		;
		;DO THREE-SOME SORT
		;
		;IF LEFT>MIDDLE, XCHG LEFT&MIDDLE
		;
		CALL	QL_SORT2
		;
		;IF LEFT > RIGHT, XCHG LEFT&RIGHT
		;
		MOV	EDI,QRIGHT_PTR
		CALL	QL_SORT2
		;
		;LASTLY, IF MIDDLE > RIGHT, XCHG MIDDLE&RIGHT
		;
		MOV	ESI,QMIDDLE_PTR
		CALL	QL_SORT2

		CMP	QDELTA,3
		JZ	QUICK3
		;
		;NOW XCHG MIDDLE WITH RIGHT-1
		;
		CALL	DEC_RIGHT_ESDI

		CALL	QEXCHANGE2

		MOV	EAX,QRIGHT_NUMBER		;SAVE RIGHTY
		;
		;DEFINE TEST SYMBOL FROM RIGHT END (ORIGINALLY FROM MIDDLE)
		;
		MOV	EBX,[EDI]	;GET RIGHT SYMBOL VALUE

		PUSH	EAX
		CALL	DEC_RIGHT_ESDI

		MOV	ESI,QLEFT_PTR
		CALL	INC_LEFT_DSSI
		;
		;SCAN FROM LEFT UNTIL SOMETHING FOUND >= CX:BX
		;
		MOV	EDX,QLEFT_NUMBER
QNL_AGAIN:
QNL_LOOP:
		;
		;COMPARE LEFT SYMBOL
		;
		MOV	EAX,[ESI]
		ADD	ESI,8

		CMP	EAX,EBX
		JNC	QNL_TRY_RIGHT
QNL_NEXT:
		LEA	EAX,[EDX+1]
		INC	EDX

		TEST	EAX,PAGE_SIZE/8 - 1
		JNZ	QNL_LOOP

		MOV	ESI,EDX
		CALL	Q_SET_LEFT_BLOCK

		JMP	QNL_LOOP

QNL_TRY_RIGHT:
		;
		;OOPS, CHANGE AND SCAN FROM OTHER DIRECTION
		;
		MOV	QLEFT_NUMBER,EDX
		SUB	ESI,8

		MOV	EDX,QRIGHT_NUMBER
		MOV	QLEFT_PTR,ESI
		;
		;SCAN FROM RIGHT UNTIL SOMETHING FOUND <= CX:BX
		;
QNR_LOOP:
		MOV	EAX,[EDI]
		SUB	EDI,8

		CMP	EAX,EBX
		JBE	QNR_SWAP
QNR_NEXT:
		MOV	EAX,EDX
		DEC	EDX

		TEST	EAX,PAGE_SIZE/8 - 1
		JNZ	QNR_LOOP

		MOV	EDI,EDX
		CALL	Q_SET_RIGHT_BLOCK

		JMP	QNR_LOOP

QNR_SWAP:
		;
		;SWAP INDEXES IN TABLE PLEASE
		;
		ADD	EDI,8
		MOV	EAX,QLEFT_NUMBER

		MOV	QRIGHT_NUMBER,EDX
		CMP	EAX,EDX

		JNC	QN_DONE1		;SAME, CANNOT SWAP

		CALL	QEXCHANGE2
		;
		;MOVE BOTH POINTERS
		;
		CALL	DEC_RIGHT_ESDI

		CALL	INC_LEFT_DSSI

		MOV	EDX,QLEFT_NUMBER
		MOV	EAX,QRIGHT_NUMBER

		CMP	EAX,EDX
		JAE	QNL_AGAIN		;JUMP IF ANY LEFT
QN_DONE1:
		;
		;SWAP R+1 WITH ORIGINAL PTR...
		;
		POP	EDI		; THIS BECOMES i

		PUSH	EDI
		CALL	Q_SET_RIGHT_BLOCK

		CALL	QEXCHANGE2		;SWAP THEM...
		;
		;DETERMINE WHICH HALF WILL BE PROCESSED...(WE WANT TO DO SMALLER HALF)
		;
		POP	ECX		;ORIGINAL RIGHTY - WHERE MIDDLE WAS STORED
		POP	EDX		;ORIGINAL LEFT

		INC	ECX
		MOV	EAX,QRIGHT_NUMBER

		MOV	EBX,ECX
		MOV	EDI,QLEFT_NUMBER

		SUB	EAX,EDX
		SUB	EBX,EDI

		CMP	EAX,EBX
		JC	QN_DONE2
		;
		;LETS SAY DO SECOND HALF FIRST
		;
		MOV	EAX,QRIGHT_NUMBER
		PUSH	EDX		;SAVE ORIGINAL LEFT NUMBER

		PUSH	EAX		;RIGHT TO USE THERE
		LEA	ESI,[EDI+1]

		MOV	EDI,ECX
		CALL	QUICK_LIN

		POPM	EDI,ESI

		MOV	ECX,EDI
		JMP	QUICK_LIN_1

QN_DONE2:
		;
		;LETS SAY DO FIRST HALF FIRST
		;
		INC	EDI
		MOV	ESI,EDX

		PUSH	EDI
		PUSH	ECX

		MOV	EDI,QRIGHT_NUMBER
		CALL	QUICK_LIN

		POPM	EDI,ESI

		MOV	ECX,EDI
		JMP	QUICK_LIN_1

QUICK_LINNUM_1	ENDP


INIT_RES_SORT	PROC
		;
		;
		;
		XOR	ECX,ECX
		ADD	EAX,4

		MOV	QN_PTR,EAX		;PLACE FOR BLOCK #'S
		MOV	[EAX-4],ECX

		JMP	QUICK_ANOTHER_BLOCK

INIT_RES_SORT	ENDP


STORE_RES_ECXEAX	PROC
		;
		;
		;
		MOV	EDX,QN_PTR1

		CMP	EDX,QN_PTR1_LIMIT
		JZ	L5$
L1$:

		MOV	[EDX],EAX
		MOV	[EDX+4],ECX

		ADD	EDX,8

		MOV	QN_PTR1,EDX

		RET

L5$:
		PUSHM	ECX,EAX

		CALL	QUICK_ANOTHER_BLOCK

		MOV	EDX,EAX
		POPM	EAX

		POP	ECX
		JMP	L1$

STORE_RES_ECXEAX	ENDP


QSORT_INIT	PROC	NEAR
		;
		;DO SETUP FOR A QUICKSORT
		;
		;HOW MANY LINNUMS ARE THERE?
		;
		;DO SETUP FOR A QUICKSORT
		;
		JMP	INIT_FINAL

L405$:
		CALL	QUICK_ANOTHER_BLOCK
INIT_FINAL:
		MOV	EDX,QN_PTR1
		MOV	ECX,QN_PTR1_LIMIT

		CMP	EDX,ECX
		JZ	L405$
L406$:
		XOR	EAX,EAX			;MARK END OF INDEXES WITH A ZERO

		MOV	[EDX],EAX
		MOV	[EDX+4],EAX

		LEA	EDI,[EDX+PAGE_SIZE+8]
		MOV	EDX,QN_BUFFER_PTR
		;
		;HOW MANY SYMBOLS ARE THERE?
		;
		MOV	ECX,QN_PTR1_LIMIT
		ADD	EDX,8

		SUB	EDI,ECX
		MOV	EAX,QN_PTR

		SHR	EDI,3
		SUB	EAX,EDX

		SHL	EAX,PAGE_BITS-2
		XOR	ESI,ESI

		ADD	EDI,EAX

		MOV	QN_COUNT,EDI
		SUB	EDI,2
		;
		;EDI IS # OF SYMBOLS
		;
		RET

QSORT_INIT	ENDP


QUICK_ANOTHER_BLOCK	PROC	NEAR	PRIVATE
		;
		;ES:DI:AX
		;
		MOV	EDX,QN_PTR
		CALL	GET_NEW_LOG_BLK	;CAN STAY IN FASTER MEMORY...

		MOV	[EDX],EAX
		ADD	EDX,4

		MOV	QN_PTR,EDX

		MOV	DPTR [EDX],0

		LEA	EDX,[EAX+PAGE_SIZE]

		MOV	QN_PTR1_LIMIT,EDX
		MOV	QN_PTR1,EAX

		RET

QUICK_ANOTHER_BLOCK	ENDP


Q_SET_LEFT_BLOCK	PROC	NEAR	PRIVATE
		;
		;ESI IS LINNUM #
		;SET ESI TO BE LEFT POINTER...
		;
		PUSH	ECX
		MOV	EAX,ESI

		SHR	EAX,PAGE_BITS-3
		MOV	ECX,QN_BUFFER_PTR

		AND	ESI,PAGE_SIZE/8-1

		SHL	ESI,3
		MOV	EAX,[ECX+EAX*4+4]

		POP	ECX
		ADD	ESI,EAX		;LOGICAL BLOCK ADDRESS

		RET

Q_SET_LEFT_BLOCK	ENDP


Q_SET_RIGHT_BLOCK	PROC	NEAR	PRIVATE
		;
		;SET ES:DI TO BE RIGHT POINTER...
		;
		PUSH	ECX
		MOV	EAX,EDI

		SHR	EAX,PAGE_BITS-3
		MOV	ECX,QN_BUFFER_PTR

		AND	EDI,PAGE_SIZE/8 - 1

		SHL	EDI,3
		MOV	EAX,[ECX+EAX*4+4]		;LOGICAL BLOCK ADDRESS

		POP	ECX
		ADD	EDI,EAX

		RET

Q_SET_RIGHT_BLOCK	ENDP


Q_SET_MIDDLE_BLOCK	PROC	NEAR	PRIVATE
		;
		;SET ES:DI TO BE RIGHT POINTER...
		;
		MOV	EAX,ECX
		MOV	EDI,ECX

		PUSH	ECX
		MOV	ECX,QN_BUFFER_PTR

		SHR	EAX,PAGE_BITS - 3
		AND	EDI,PAGE_SIZE/8 - 1

		SHL	EDI,3
		MOV	EAX,[ECX+EAX*4+4]

		POP	ECX
		ADD	EDI,EAX		;LOGICAL BLOCK ADDRESS

		RET

Q_SET_MIDDLE_BLOCK	ENDP


QL_SORT2	PROC	NEAR
		;
		;SORT [DS:SI] VS [ES:DI]
		;
		MOV	EAX,[ESI]
		MOV	ECX,[EDI]

		CMP	EAX,ECX
		JA	L2$

		RET

QEXCHANGE2::
		MOV	EAX,[ESI]
		MOV	ECX,[EDI]
L2$:
		MOV	[EDI],EAX
		MOV	[ESI],ECX

		MOV	EAX,[ESI+4]
		MOV	ECX,[EDI+4]

		MOV	[EDI+4],EAX
		MOV	[ESI+4],ECX

		RET

QL_SORT2	ENDP


DEC_RIGHT_ESDI	PROC	NEAR	PRIVATE
		;
		;
		;
		MOV	EAX,QRIGHT_NUMBER
		SUB	EDI,8

		TEST	EAX,PAGE_SIZE/8 - 1
		JZ	L9$

		DEC	EAX

		MOV	QRIGHT_NUMBER,EAX

		RET

L9$:
		DEC	EAX

		MOV	QRIGHT_NUMBER,EAX
		MOV	EDI,EAX

		JMP	Q_SET_RIGHT_BLOCK

DEC_RIGHT_ESDI	ENDP


INC_LEFT_DSSI	PROC	NEAR	PRIVATE
		;
		;
		;
		MOV	EAX,QLEFT_NUMBER
		ADD	ESI,8

		INC	EAX

		MOV	QLEFT_NUMBER,EAX
		TEST	EAX,PAGE_SIZE/8 - 1

		JZ	L9$

		RET

L9$:
		MOV	ESI,EAX
		JMP	Q_SET_LEFT_BLOCK

INC_LEFT_DSSI	ENDP


		.DATA?

		ALIGN	4

QN_PTR		DD	?
QN_PTR1		DD	?
QN_PTR1_LIMIT	DD	?

endif


		END

